Tree Search
Many problems can be represented in the form of a search tree.
An example is finding a road path between two cities.
-
The generator produces the list of cities connected to the current city.
-
The test determines if the listed city is the destination city.
Trees used in tree search can quickly become very large, consuming
large amounts of computer memory and requiring large amounts of
processing time to search. Knowledge about the problem domain is used
to choose an appropriate tree search technique.
Breadth-First Search
In breadth-first search the starting (root) node is first
expanded, then all these generated nodes are expanded,
then their successors, and so on.
Depth-First Search
In depth-first search the expanded node is always at the lowest level
of the tree. After a dead end is reached the next-lowest level node
is expanded.
Best-First Search
Neither breadth-first nor depth-first search use information from the
evaluation function to help determine which node should be expanded
next. Best-first search sorts the generated nodes based on the
evaluation function result.
In our road path example the evaluation function can return the
crows-flight distance between the current city and the destination city.
If the destination is Redwood City,
best-first search will expand the Menlo Park node first since it is
closer to Redwood City.
Breadth-and-Depth-first search images and definitions based on
[Russell and Norvig, 1995]
back
index
forward